Stone Matrix Asphalt (SMA) is a gap-graded mix that is gaining popularity worldwide. Generally, gap graded mixes are thought to be weak in fatigue resistance. In this study, cellulose fibers were pre-blended in PG64-22 binder with fiber proportions of 0.2%, 0.4%, 0.6%, 0.8% and 1.0% by weight of aggregates. The fiber-modified binder showed improved rheological properties and showed that the PG64-22 binder can be modified and raised to PG70-22 grade. The cellulose oil palm fiber (COPF) was found to improve the diameteral fatigue performance of SMA design mix. The fatigue life increased to a maximum at a fiber content of about 0.6%, whilst the tensile stress and stiffness also showed a similar trend in performance. The initial strains of the mix were lowest at a fiber content of 0.6%.